1. Field of the Invention
This invention relates generally to computing system data storage subsystems having cache memory and, more particularly, to destaging modified data blocks from a cache memory.
2. Description of the Related Art
Computing systems frequently are provided with storage subsystems having multiple storage devices connected to the computing system central processor through a device controller. For example, some computing systems include a plurality of disks arranged into a disk array with parity and sparing. Parity refers to organizing data into parity groups such that each modification of disk data that involves a relatively small write operation requires a read old data, read old parity, write new data, write new parity sequence of operations often referred to as a read-modify-write sequence. Sparing refers to providing spare data blocks to be used in the event of a disk failure. A disk array controller is provided between the disk array and the computing system central processor unit (CPU) and includes a non-volatile cache memory.
A cache memory provides a fast, limited-size temporary storage for data and can reduce the number of times a disk must be accessed to retrieve a requested data block. As applications running in the central processor unit request blocks of data from the disk array, the disk array controller checks a cache directory to determine if a copy of the requested data block is in the cache memory of the controller. If the disk array controller determines that the cache memory contains the most recent copy of the data block, referred to as a cache hit, then the controller provides the data block to a requesting application from the cache memory rather than from the particular disk where the data block is located.
If the most recent copy of the data block is not in the cache memory, referred to as a cache miss, then the disk array controller consults the cache memory directory to find a cache memory location containing a block that can be replaced, or overwritten, because the data in that location also resides on a disk. The controller reads a copy of the requested data block from the disk and puts it in the cache memory location to be overwritten. Lastly, the controller updates the cache directory to indicate that the old data block is no longer in the cache memory location and that the new data block has taken its place. Once the new data block is in the cache memory, it can be modified and updated.
Disk arrays with cache memory are desirable because they increase efficiency of expensive computing systems by reducing the number of times data blocks must be accessed from a disk. Accesses of data from a disk are typically slower than accesses of data from a cache memory. Therefore, getting data from a cache memory permits a computing system to carry out processing faster than is possible when getting the data from a disk. This increased efficiency reduces the cost of operations.
As described above, as applications update blocks of data with new data values, the disk array controller writes the new data values into the data block copies in the cache memory. When a new data value is written to a data block copy in the cache memory, the cache copy is said to be modified, or dirty, because the information stored in the cache memory copy is different from the information stored for the data block on disk. There is no urgency to return the dirty data block to the disk before a power interruption or the like because the cache memory is non-volatile and therefore the modified data will not be lost. It is important, however, to return a dirty block to disk before it is replaced or overwritten with a new data block, because the modified data otherwise would be lost.
It can be useful to keep dirty blocks in cache memory for as long as possible for a variety of reasons. First of all, if applications write again and again to the same data block, then the writing operation can take place between the CPU and the cache memory rather than between the CPU and the disk array. Thus, no disk read/write operation is necessary. In this way, disk access operations are reduced and storage system efficiency is increased. Secondly, if dirty blocks are kept in cache for some time, then groups of dirty blocks can be returned to disk locations during the same disk operation, with the read-modify-write sequence of parity operations multiplexed and overlapped to minimize disk utilization. Again, disk accesses are reduced and efficiency is increased.
Writing dirty blocks from cache memory back to their corresponding disk locations is known as destaging. As noted above, such destaging must take place before a data value can be overwritten in the cache memory. A disk controller with a cache memory includes a cache manager that controls the destaging. Most conventional destaging schemes are relatively simple and utilize a least-recently-used (LRU) ordering of the cache memory locations. An LRU ordering of the cache memory can be represented as a stack in which the most recently used data block cache locations are at the top of the stack and the least recently used, or oldest, data blocks are at the bottom of the stack. A typical cache manager would begin destaging dirty blocks when a predetermined percentage of the cache locations contain dirty blocks, such as 50%, and would begin destaging from the bottom of the stack, with the oldest data blocks being returned to disk first.
Other schemes for determining when to begin destaging also are used. For example, some cache managers begin destaging when a particular data block becomes the least recently used block (the bottom of the stack). Other cache managers might begin destaging when a particular disk has not had a read request within a specified time interval, such as within the previous ten milliseconds. Still other cache managers might begin destaging when a disk has not moved its read/write arm within a specified time interval. Typically, such destaging schemes seek to maximize cache hit rates or minimize disk queue wait times. In either case, the goal is to provide relatively fast response to read requests.
Several schemes also are used to determine when to stop destaging. Most are analogous to the scheme used to determine when to begin destaging. In the first example given above for beginning when the percentage of dirty cache blocks is greater than a first predetermined number, the cache manager would stop destaging when the percentage of dirty blocks falls below a second predetermined number. Similarly, other schemes might stop destaging when a read request is received by a disk that was previously in the process of destaging. Once again, the goal is to provide good response times to read requests.
The decision of what blocks are to be destaged from cache memory is usually straightforward. For example, a typical cache manager might destage a predetermined number of blocks in order of least recently used blocks (from the bottom of the stack and up). Alternatively, a cache manager might destage all dirty blocks that are close together physically on a disk or might destage the LRU data block at the bottom of the stack and all other dirty blocks that are physically close to it on the same disk. The manner in which destaging is carried out also is relatively straightforward, comprising either a read-modify-write sequence or, alternatively, a read-remainder of parity group, write new data, write new parity sequence. Usually, the selection is made depending on which sequence requires less work by the disk system.
The destaging schemes described above tend to be invariant. That is, the cache manager is provided with one relatively simple decision criteria for determining when to begin destaging, what to destage, when to stop destaging, and how to carry out the destaging. Utilization of various cache memory locations and storage devices can change with time. It would be advantageous to provide a more flexible approach to controlling destaging that can adapt to changing cache memory usage, provides good response times to requests for disk reads, and maximizes cache hit rates. It also would be desirable to provide increased efficiency in destaging by taking into account the geographic location of blocks within the storage devices so that the number of storage device operations necessary for destaging is reduced.
From the discussion above, it should be apparent that there is a need for a storage system that permits increased flexibility in controlling destaging and provides increased system efficiency. The present invention satisfies this need.